/**
 * Greatest Common Divisor
 * 
 * @author Jon Ludwig
 */

import java.math.BigInteger;


public class GCD {
	
	/**
	 * Performs Euclids GCD algorithm
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public static BigInteger Euclidean(BigInteger a, BigInteger b)
	{
		if (b.compareTo(BigInteger.ZERO) == 0)
			return a;
		
		return Euclidean(b, a.mod(b));
	}
	
	/**
	 * Performs the Extended Euclidean algorithm to calculate the GCD
	 * as well as the modular inverses.
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public static BigInteger[] ExtEuclidean(BigInteger a, BigInteger b)
	{
		/*
		 * res[0] = x
		 * res[1] = y
		 * res[2] = d
		 * ax + by = d = gcd(a, b)
		 */
		BigInteger[] res = new BigInteger[3];
		
		if (b.compareTo(BigInteger.ZERO) == 0) {
			res[0] = BigInteger.ONE;
			res[1] = BigInteger.ZERO;
			res[2] = a;
		}
		else {
			BigInteger[] temp = ExtEuclidean(b, a.mod(b));
			res[0] = temp[1];
			res[1] = temp[0].subtract(temp[1].multiply(a.divide(b)));
			res[2] = temp[2];
		}
		
		return res;
	}
	
	/**
	 * Main entry point
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		if (args.length < 2) {
			System.out.println("usage: java GCD a b");
			return;
		}
		
		BigInteger a, b;
		a = new BigInteger(args[0]);
		b = new BigInteger(args[1]);
		
		BigInteger gcd[] = ExtEuclidean(a, b);
		
		System.out.println(a + "*" + gcd[0] + " + " + b + "*" + gcd[1] + " = " + gcd[2]);
	}

}
